#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <typeinfo>
using namespace std;

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//打印链表
void displayList(ListNode *p){
    while( p ){
        cout<< p->val ;
        p = p->next;
        if(p) cout<<"->";
    }
    cout<<endl;
}

//解决方案类
class Solution {
public:
    string addBinary(string a, string b) {
        int n1=a.length(), n2=b.length();
        int p1=n1-1 , p2 = n2 -1;
        char c = '0';
        string rt="";
        while(p1>=0 || p2 >=0 ){
            char c1 = p1>=0 ? a.at(p1) : '0' ;
            char c2 = p2>=0 ? b.at(p2) : '0' ;
            char c3 = c1-'0'+c2-'0'+c-'0';
            c = c3/2+'0';
            c3 = c3%2 + '0';
            rt = (c3=='1'?"1"+rt:"0"+rt);
            p1--;
            p2--;
        }
        rt = c=='1'? "1" +rt:rt;
        return rt;
    }
};
int main(){
    Solution sp;
   // ListNode *l1 = new ListNode(1,new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(3)))));
    string a="101",b="1";
    cout<<sp.addBinary(a,b)<<endl;

    return 0;
}